☆
An average case NP-complete graph colouring problem
https://arxiv.org/abs/cs/0112001v10
Authors: Leonid A. Levin, Ramarathnam Venkatesan
Liked by: Sergey Kirgizov
Domains: Computational Complexity (cs.CC)
Tags: NP-complete, graph coloruing
Uploaded by: Sergey Kirgizov
Upload date: 2019-09-26 14:01:16

Comments:

Although certain NP-complete problems stay hard even on average input, some NP-complete problems are only hard in rare cases. Such NP-complete problems can provably be resolved very quickly on average case under some probability distributions over all possible inputs. **1. What is the average case of a real-world graph ? ** **2. How to properly define a suitable probability distribution for real-world graphs ? **
Reply
Sergey Kirgizov at 2019-09-26 14:10:14
Edited by Sergey Kirgizov at 2019-09-26 14:18:52

Please consider to register or login to comment on the paper.